#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;



//method 1
void getNqueens(int level, vector<int> &pos, vector<vector<string> > &ans, vector<int> &a, vector<int> &b, vector<int> &c)
{
    if (level == pos.size()) {
        vector<string> rtn;
        for (int i = 0; i < pos.size(); i++) {
            string str;
            for (int j = 0; j < pos.size(); j++) {
                if (j != pos[i]) { 
                    str += '.'; 
            //        cout << '.' << " ";
                } else { 
                    str += 'Q'; 
              //      cout << "Q" << " ";
                }
            }
          //  cout << endl;
            rtn.push_back(str);
        }
        ans.push_back(rtn);
        return;
    }

   for (int i = 0; i < pos.size(); i++) {
      if (a[i] || b[level+i] || c[level-i+pos.size()-1]) continue;
      a[i] = 1;
      b[level+i] = 1;
      c[level-i+pos.size()-1] = 1;
      pos[level] = i;
      getNqueens(level+1, pos, ans, a, b, c);
      a[i] = 0;
      b[level+i] = 0;
      c[level-i+pos.size()-1] = 0;
   }
}

class Solution {
    public:
        vector<vector<string> > solveNQueens(int n) {
            vector<vector<string> > ans;                        
            vector<int> pos(n,0);
            vector<int> a(n, 0);
            vector<int> b(2*n-1, 0);
            vector<int> c(2*n-1, 0);
            getNqueens(0, pos, ans, a, b, c); 
            return ans;
        }
};

//add better code for this
void dfs(int index, vector<bool> &colHash, vector<bool> &diagHash, vector<bool> &diagHash2, vector<string> &cur, vector<vector<string> > &ans)
{
    if (index == colHash.size()) {
        ans.push_back(cur);
        return;
    }   

    for (int i = 0; i < colHash.size(); i++) {
        if (colHash[i] || diagHash2[index - i + colHash.size()-1] || diagHash[index+i]) continue;
        colHash[i] = true;
        diagHash2[index - i + colHash.size()-1] = true;
        diagHash[index+i] = true;
        cur[index][i] = 'Q';
        dfs(index+1, colHash, diagHash, diagHash2, cur, ans);
        cur[index][i] = '.';
        colHash[i] = false;
        diagHash2[index - i + colHash.size()-1] = false;
        diagHash[index+i] = false;
    }   

}


class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<bool> colHash(n, false);
        vector<bool> diagHash(2*n-2, false);
        vector<bool> diagHash2(2*n-2, false);
        vector<vector<string> > ans;
        vector<string> cur(n, string(n, '.'));
        dfs(0, colHash, diagHash, diagHash2, cur, ans);
        return ans;        
    }
};


//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    mySolution.solveNQueens(2);   
    return 0;
}
